/*
循环链表解决约瑟夫环问题
*/
#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* next = NULL;
	Node(int value):data(value){};
	Node(){};
};

class JosephCircle
{
	Node* tail;
public:
	JosephCircle(){tail = NULL;}
	~JosephCircle(){delete tail;}
	void Add(int num);		//向循环链表中添加一个编号尾num的人
	void Print();			//打印循环链表的值
	void Eliminate(int step);	//以步长为step淘汰
};
void JosephCircle::Add(int num){
	if(tail == NULL){
		tail = new Node(num);
		tail->next =tail;
	}
	else{
		Node* new_node = new Node(num);
		new_node->next = tail->next;
		tail->next = new_node;
		tail = new_node;
	}
}
void JosephCircle::Eliminate(int step){
	Node* cur = tail;
	while(cur != NULL && cur->next != cur){
		for(int i = 0;i < step-1;i++){
			cur = cur->next;
		}
		Node* eliminate = cur->next;
		cur->next = eliminate->next;
		if(eliminate == tail){
			tail = cur;
		}
		cout<<"deleting  "<<eliminate->data<<endl;
		delete eliminate;
		Print();
	}
}
void JosephCircle::Print(){
	Node* cur = tail;
	while(cur != NULL){			//打印的妙呀，记牢
		cur = cur->next;
		cout<<cur->data<<"  ";
		if(cur == tail){
			break;
		}
	}
	cout<<endl;
}

int main(int argc, char const *argv[])
{
	JosephCircle jc;
	for(int i = 1;i <= 6;i++){//注意边界条件
		jc.Add(i);
	}
	jc.Eliminate(3);
	return 0;
}